package test.lrucache;

import java.util.HashMap;
import java.util.Map;

public class LRUCache2 {

    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node() {

        }
        Node(int key, int value) {
            this.key=key;
            this.value=value;
        }
    }

    private Map<Integer, Node> map;

    private Node head;
    private Node tail;

    private int capacity;
    private int size;

    public LRUCache2(int capacity) {
        this.map = new HashMap<>(capacity);

        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;

        this.capacity = capacity;
        this.size = 0;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node != null) {
            deleteNode(node);
            appendLast(node);
            return node.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            if (size >= capacity) {
                //删除头结点
                Node delete = head.next;
                deleteNode(delete);
                map.remove(delete.key);
            } else {
                size++;
            }
            Node newNode = new Node(key,value);
            appendLast(newNode);
            map.put(key, newNode);
        } else {//node!=null
            node.value = value;
            deleteNode(node);
            appendLast(node);
        }
    }

    private void appendLast(Node node) {
        //将node放到最后
        node.prev = tail.prev;
        node.next = tail;
        node.prev.next = node;
        node.next.prev = node;
    }

    private void deleteNode(Node node) {
        //删除node
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}
